package tests;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class Test151 {

    public static void main(String[] args) {
        int[] nums = {2,2,2,2,2};
        System.out.println(fourSum(nums, 8));
    }
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i]==nums[i-1]) {
                continue;
            }
            for(int j = i + 1; j < nums.length; j++) {
                if (j > i+1 && nums[j]==nums[j-1]) {
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;

                while(left < right) {
                    if(nums[i]+nums[j]+nums[left]+nums[right] > target) {
                        right--;
                    }else if(nums[i]+nums[j]+nums[left]+nums[right] < target) {
                        left++;
                    }else {
                        ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while(left < right && nums[left]==nums[left+1]) left++;
                        while(left < right && nums[right]==nums[right-1]) right--;
                        left++;
                        right--;
                    }
                }
            }
        }
        return ret;
    }

    public static void main4(String[] args) {
        int count = 1_0000_0000;// 比较次数 100000000次
        Random random = new Random();// 生成随机数字
        boolean flag = true;// 相等则为 true

        for (int i = 0; i < count; i++) {
            int num1 = random.nextInt(Integer.MAX_VALUE/2);// 随机正数
            int num1_2 = random.nextInt(Integer.MAX_VALUE/2);// 随机正数
            // 随机正数 + 随机正数
            if ((num1+num1_2) != addAB(num1,num1_2)){
                // 有一次不相等的，则退出循环
                flag = false;
                break;
            }
            int num2 = -random.nextInt(Integer.MAX_VALUE/2);// 随机负数
            int num2_2 = -random.nextInt(Integer.MAX_VALUE/2);// 随机负数
            // 随机负数  + 随机负数
            if ((num2+num2_2) != addAB(num2,num2_2)){
                // 有一次不相等的，则退出循环
                flag = false;
                break;
            }

            int num3 = random.nextInt(Integer.MAX_VALUE);// 随机正数
            int num4 = -random.nextInt(Integer.MAX_VALUE);// 随机负数
            // 随机正数  + 随机负数
            if ((num3+num4) != addAB(num3,num4)){
                // 有一次不相等的，则退出循环
                flag = false;
                break;
            }
        }
        System.out.println(flag);
    }
    public static int addAB(int A, int B) {
        while ((A & B) != 0) {
            int A_B = A ^ B;// 无进位求和
            int AB = (A & B) << 1;// 进位
            A = A_B;
            B = AB;
        }
        return (A ^ B);
    }


    public static void main3(String[] args) {
        String s = "fmn";
        s.toUpperCase();
        String y = s.replace('f','F');
        System.out.println(y);

//        int i = 0;
//        Integer j = new Integer(0);
//        System.out.println(i == j);
//        System.out.println(j.equals(i));

        Integer i1 = new Integer(12);
        Integer i2 = new Integer(12);
        System.out.println(i1 == i2);
    }

    public static void main2(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        List<List<Integer>> lists = threeSum(nums);
        System.out.println(lists);
    }
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();

        for(int i = 0; i < nums.length; i++) {
            // 去重
            if(i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            if(left >= nums.length) {
                break;
            }
            while (left < right) {
                if(nums[i]+nums[left]+nums[right] > 0) {
                    right--;
                }else if(nums[i]+nums[left]+nums[right] < 0) {
                    left++;
                }else {
                    ret.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    right--;
                    left++;
                }
            }
        }
        return ret;
    }

    public static void main1(String[] args) {
        reverseWords("  hello world  ");
    }
    public static String reverseWords(String s) {
        StringBuilder sb = deleteSpace(s);
        reverse(sb,0,sb.length()-1);

        sb.append(" ");
        // 单独翻转每个区间
        int begin = 0;
        int end = 0;
        while(end < sb.length()) {
            if(sb.charAt(end) != ' ') {
                end++;
            }else {
                reverse(sb,begin,end-1);
                end++;
                begin = end;
            }
        }
        return sb.substring(0,sb.length()-1).toString();
    }
    // 反转 左闭右闭区间
    public static void reverse(StringBuilder sb,int start,int end) {
        while(start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start,sb.charAt(end));
            sb.setCharAt(end,temp);
            start++;
            end--;
        }
    }
    // 去掉前后中多余的空格
    public static StringBuilder deleteSpace(String s) {
        int start = 0;
        int end = s.length() - 1;
        // 去掉前置空格
        while(s.charAt(start) == ' ') {
            start++;
        }
        // 去掉后置空格
        while(s.charAt(end) == ' ') {
            end--;
        }
        // 去掉中间空格
        StringBuilder sb = new StringBuilder();
        while(start <= end) {
            char c = s.charAt(start);
            if(c != ' ' || s.charAt(start-1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        return sb;
    }
}
